import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-04-04
 * Time: 21:08
 */
class Solution {
    public void sortColors(int[] nums) {
        //写一个快速排序
        QuickSort(nums,0,nums.length-1);
    }
    private void QuickSort(int[] nums,int left,int right) {
        if(left>=right) {
            return ;
        }
        int mid = parition(nums,left,right);
        QuickSort(nums,left,mid-1);
        QuickSort(nums,mid+1,right);
    }
    private int parition(int[] a,int left,int right) {
        int begin = left;
        int end = right;
        int pivot = a[begin];
        while(begin< end) {
            //右边找小放到左边
            while(begin<end&&a[end]>=pivot) {
                end--;
            }
            a[begin] = a[end];
            //左边找大放到右边
            while(begin<end&&a[begin]<=pivot) {
                begin++;
            }
            a[end] = a[begin];
        }
        //最后begin和end相遇 把坑的元素放到两者相遇的地方
        a[begin]  =pivot;
        return end;
    }
}
public class TestDemo {
    public static void main(String[] args) {
        int[] array ={1,5,8,6,0,3,8,7,5,2,0,5};
        Solution solution =new Solution();
        solution.sortColors(array);
        System.out.println(Arrays.toString(array));
    }

}
